package oj.oj_100;
/**
 * 相同的树
 * https://leetcode.cn/problems/same-tree/
 */

import oj.oj_144.TreeNode;

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            // 两个都是空树，所以
            return true;
        }

        // 只能是以下三种情况:
        // 1) p == null && q != null
        // 2) p != null && q == null
        // 3) p != null && q != null
        if (p == null || q == null) {
            // 一定是 1) 或者 2) 的情况
            // 说明一个是空树，一个不是空树
            return false;
        }

        // p != null && q != null
        // 两棵树相同 <-> 根的值相同 && 左子树相同 && 右子树相同
        if (p.val != q.val) {
            // 根的值不一样，没有继续比较的意义了
            return false;
        }

        boolean r = isSameTree(p.left, q.left);
        if (r == false) {
            // 说明两棵树的左子树不相同，没有继续比较的意义了
            return false;
        }

        r = isSameTree(p.right, q.right);
        if (r == true) {
            // 根的值一样 && 左子树一样 && 右子树一样
            return true;
        } else {
            // 说明两棵树的右子树不相同，
            return false;
        }

        // return p.val == q.val
        //     && isSameTree(p.left, q.left)
        //     && isSameTree(p.right, q.right);
    }
}
